package leetcode.每日一题;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.Comparator;

/**
 * @author ：zsy
 * @date ：Created 2022/12/17 8:21 PM
 * @description：
 */
public class 通过连接另一个数组的子数组得到一个数组 {
    @Test
    public void test() {
        CommonUtils.arrTransfer("[[7122186,-6877645,3486322],[-8477030],[1917773],[-9337589],[7017586],[-4492418],[-745836],[-912773],[9818463,4180029],[-4576693,-6690524,-7751890],[-7659435],[4847283]]");
        System.out.println(new Solution().canChoose(new int[][]{{7122186,-6877645,3486322},{-8477030},{1917773},{-9337589},{7017586},{-4492418},{-745836},{-912773},{9818463,4180029},{-4576693,-6690524,-7751890},{-7659435},{4847283}},
                new int[]{3486322,7122186,-6877645,3486322,-8477030,1917773,-9337589,7017586,-4492418,-745836,-912773,9818463,4180029,-4576693,-6690524,-7751890,1917773,-7659435,4847283}));
    }

    /*class Solution {
        public boolean canChoose(int[][] groups, int[] nums) {
            int first = 0;
            int firstFromEnd = 0;
            boolean flag = false;
            for (int[] group : groups) {
                int[] dp = new int[nums.length - first + 1];
                for (int g : group) {
                    for (int i = nums.length - 1; i >= first ; i--) {
                        int dpIdx = i - first;
                        if (nums[i] == g) {
                            dp[dpIdx] = (dpIdx > 0 ? dp[dpIdx - 1] : 0) + 1;
                        }
                        if (dp[dpIdx] == group.length) {
                            firstFromEnd = i + 1;
                            flag = true;
                        }
                    }
                }
                if (flag) {
                    first = firstFromEnd;
                    flag = false;
                } else {
                    return false;
                }
            }
            return true;
        }
    }*/

    class Solution {
        public boolean canChoose(int[][] groups, int[] nums) {
            int i = 0;
            for (int k = 0; k < nums.length && i < groups.length;) {
                if (check(groups[i], nums, k)) {
                    k += groups[i].length;
                    i++;
                } else {
                    k++;
                }
            }
            return i == groups.length;
        }

        private boolean check(int[] g, int[] nums, int k) {
            if (k + g.length > nums.length) return false;
            for (int i = 0; i < g.length; i++) {
                if (nums[i + k] != g[i]) {
                    return false;
                }
            }
            return true;
        }
    }
}
